package LimitedTimeGame.Day_0303;

/**
 * @author zxc
 * @date 2023/03/03 10:36
 **/

/**
 * 题目 ：两数相加
 * 题目详述 ：
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头
 *
 * 提示：
 * 每个链表中的节点数在范围 [1, 100] 内
 * 0 <= Node.val <= 9
 * 题目数据保证列表表示的数字不含前导零
 *
 */
public class AddTwoNumbers {
    /**
     * 思路 ：
     * ===>
     * （1）首先，需要定义一个虚拟头结点，其next指针指向链表l1;
     * （2）同时，定义一个carry变量来保存进位 && 定义一个pre节点，来保存当前正在遍历链表l1节点的上一个节点;
     * （3）while循环遍历结束条件 ：当链表l1 && 链表l2其中有一个被遍历完;
     * （4）最后，考虑进位，若是最后一位的进位carry > 0的话在，则需要在链表上加上一个节点;
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        dummy.next = l1;
        int carry = 0;
        while(l1 != null && l2 != null){
            int value = l1.val + l2.val + carry;
            carry = value / 10;
            l1.val = value % 10;
            pre = l1;
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null){
            System.out.println("1");
            int value = l1.val + carry;
            carry = value / 10;
            l1.val = value % 10;
            pre = l1;
            l1 = l1.next;
        }
        while(l2 != null){
            int value = l2.val + carry;
            carry = value / 10;
            pre.next = new ListNode(value % 10);
            pre = pre.next;
            l2 = l2.next;
        }
        System.out.println(carry);
        if(carry > 0){
            pre.next = new ListNode(carry);
            pre = pre.next;
        }
        return dummy.next;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
